//b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，bm−2 即为 b 的乘法逆元。
#include <iostream>
using namespace std;

typedef long long ll;

int n, a, p; //获取输入

inline int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int quick_pow(int a, int p, int n)
{
    ll res = 1, t = a;
    while (p)
    {
        if (p & 1)
            res = res * t % n;
        t = t * t % n;
        p >>= 1;
    }
    return res;
}

int main()
{
    cin >> n;
    while (n--)
    {
        cin >> a >> p;
        if (gcd(a, p) == 1)
            cout << quick_pow(a, p - 2, p) << endl;
        else
            cout << "impossible" << endl;
    }
}